Prime Numbers and Cryptography

Algorithms for finding prime numbers date back at least as far as ancient Greece, where mathematicians used a straightforward approach known as the Sieve of Erastothenes. The Sieve of Erastothenes works as follows: To find all the primes less than n, begin by writing down all the numbers from 1 to n in sequence. Then cross out all the numbers that are multiples of 2, besides itself (4, 6, 8, 10, 12, and so on). Take the next smallest number that hasn’t been crossed out (in this case, 3), an...

 The Explore VS Exploit Problem

In English, the words “explore” and “exploit” come loaded with completely opposite connotations. But to a computer scientist, these words have much more specific and neutral meanings. Simply put, exploration is gathering information, and exploitation is using the information you have to get a known good result. [...] [...] A sobering property of trying new things is that the value of exploration, of finding a new favorite, can only go down over time, as the remaining opportunities ...

 The Stopping Problem

The 37% Rule derives from optimal stopping’s most famous puzzle, which has come to be known as the “secretary problem.” Its setup is much like the apartment hunter’s dilemma that we considered earlier. Imagine you’re interviewing a set of applicants for a position as a secretary, and your goal is to maximize the chance of hiring the single best applicant in the pool. While you have no idea how to assign scores to individual applicants, you can easily judge which one you prefer. (A m...

 Asymmetrical Psychology: Computers Use Knights Better Tha...

e. Chess players have the most trouble visualizing the moves of knights because their move is unlike anything else in the game, an L-shaped hop instead of a predictable straight line like the other pieces. Computers, of course, don't visualize anything at all, and so manage every piece with equal skill. I believe it was Bent Larsen, the first GM victim of a computer in tournament play, who stated that computers dropped a few hundred rating points if you eliminated their knights. This is an ex...

 How a Nerd Walks Up the Stairs

Your steps should be in a cycle: short, long, long. Long in this case means a double step. Thus, you will cover five stairs in one short-long-long cycle. In addition, you should always start the first cycle on the same foot. Suppose you start on the left foot, then after two cycles you are back on the left foot, having covered ten stairs. While you are walking the stairs in this way, it is clear where you are in the cycle. By the end of the staircase, you will know the number of stairs modulo...